package com.ideas.impl.mianshi;

/**
 * @Author lijian.wu
 * @Date 2024/4/18 16:23
 * 归并排序
 */
public class MergeSort {

    void mergeSort(int[] nums, int left, int right) {
        //划分终止
        if(left >= right){
            return;
        }
        //划分阶段
        int mid = (left + right)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //合并阶段
        // 合并阶段
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        // 创建一个临时数组 tmp ，用于存放合并后的结果
        int[] tmp = new int[right - left + 1];
        // 初始化左子数组和右子数组的起始索引
        int i = left, j = mid + 1, k = 0;
        while (i<=mid || j<=right){
            if(nums[i] < nums[j]){
                tmp[k++] = nums[i++];
            }else{
                tmp[k++] = nums[j++];
            }
        }
        while(i<=mid){
            tmp[k++] = nums[i++];
        }
        while(j<=right){
            tmp[k++] = nums[j++];
        }
        //将临时数组中的值复制回nums
        for (k = 0; k < tmp.length; k++) {
            nums[left+k] = tmp[k];
        }
    }
}
